#include "FibHeap.hpp"

FibHeap_Node node_array[1001];

FibHeap::FibHeap()
{
    this->n = 0;
    this->min = nullptr;
}


/**
 * @brief 向斐波那契堆的根链表插入节点x
 * @param x 节点x
 * 
 */
void FibHeap::insert_into_rootlist(FibHeap_Node* x){
    x->right = this->min;
    x->left = this->min->left;
    x->right->left = x;
    x->left->right = x;
}


/**
 * @brief 在斐波那契堆中插入节点，节点的关键字为index
 * 
 * @param key 被插入的新节点的关键字
 * @note 将所有的节点都放到数组 node_array 里面，不使用new创建新的节点。避免类被释放时内存还在而导致内存泄漏。
 * 
 * @return 插入后堆的n
 */
int FibHeap::INSERT(int key){
    FibHeap_Node *x = &node_array[key];
    x->degree = 0;
    x->key = key;
    x->p = nullptr;
    x->child = nullptr;
    x->mark = false;

    if(this->min == nullptr){
        x->left = x;
        x->right = x;
        this->min = x;
    }

    else{
        insert_into_rootlist(x);
        if(x->key < this->min->key){
            this->min = x;
        }
    }
    this->n ++;
    return this->n;
}


/**
 * @brief 合并两个斐波那契堆
 * 
 * @param H1 第一个斐波那契堆
 * @param H2 第二个斐波那契堆
 * 
 * @return 新的斐波那契堆
 */
FibHeap UNION(FibHeap H1, FibHeap H2){
    FibHeap H = FibHeap();
    H.min = H1.min;

    //concentrate the root list H2 with the root list of H
    if (H1.min != NULL && H2.min != NULL)
    {
        H.min->left->right = H2.min->right;
        H2.min->right->left = H.min->left;
        H2.min->right = H.min;
        H.min->left = H2.min;
    }
    if(H1.min == nullptr || (H1.min != nullptr && H2.min != nullptr && H2.min->key < H1.min->key)){
        H.min = H2.min;
    }
    H.n = H1.n + H2.n;
    return H;
}


/**
 * @brief 将节点从根链表中删除
 * 
 * @param x 待删除的节点
 * @note 不会更新斐波那契堆的度
 */
void FibHeap::remove_from_rootlist(FibHeap_Node*x){
    if(x->right == x){
        //斐波那契堆中只有这一个节点
        this->min = nullptr;
    }
    else{
        if (this->min == x)
        {
            this->min = x->right;
        }
        
        x->right->left = x->left;
        x->left->right = x->right;
    }
}


/**
 * @brief 抽取最小节点
 * @return 最小节点的指针
 * @note 最小节点将会被从斐波那契堆中删除
 * 
 * @return 提取出的最小节点的key
 */
int FibHeap::EXTRACT_MIN(void){
    FibHeap_Node* z = this->min;
    if(z != nullptr){
        if(z->child != nullptr){
            for (FibHeap_Node* x = z->child; x != z->child->left;)
            {
                FibHeap_Node* temp = x;
                x = x->right;
                this->insert_into_rootlist(temp);
                temp->p = nullptr;
            }
            this->insert_into_rootlist(z->child->left);
            z->child->left->p = nullptr;
        }

        this->remove_from_rootlist(z);
        if(z == z->right){
            this->min = nullptr;
        }
        else{
            this->min = z->right;
            this->CONSOLIDATE();
        }
        this->n --;
    }
    return z->key;
}


/**
 * @brief 变换斐波那契堆使得相同父亲的不同节点的度不同
 * 
 */
void FibHeap::CONSOLIDATE(void){
    FibHeap_Node* A[DHn + 1];    //lg(1000)向上取整+1
    for (int i = 0; i <= DHn; i++)
    {
        A[i] = nullptr;
    }

    FibHeap_Node *end_left = min->left;
    for (FibHeap_Node* w = min; w != end_left;)
    {
        FibHeap_Node* x = w;
        w = w->right;
        int d = x->degree;
        while (A[d] != nullptr && A[d] != x)
        {
            FibHeap_Node* y = A[d];
            if (x->key > y->key)
            {
                FibHeap_Node* temp = x;
                x = y;
                y = temp;
            }
            LINK(y, x);
            A[d] = nullptr;
            d ++;
        }
        A[d] = x;
    }
    {
    FibHeap_Node* x = min->left;
    int d = x->degree;
    while (A[d] != nullptr && A[d] != x)
    {
        FibHeap_Node* y = A[d];
        if (x->key > y->key)
        {
            FibHeap_Node* temp = x;
            x = y;
            y = temp;
        }
        LINK(y, x);
        A[d] = nullptr;
        d ++;
    }
    A[d] = x;
    }

    this->min = nullptr;
    for (int i = 0; i <= DHn; i++)
    {
        if (A[i] != nullptr)
        {
            if (this->min == nullptr)
            {
                A[i]->left = A[i];
                A[i]->right = A[i];
                this->min = A[i];
            }
            else{
                insert_into_rootlist(A[i]);
                if(A[i]->key < this->min->key){
                    this->min = A[i];
                }
            }
        }
    }
}


/**
 * @brief 将y从根链表中删除并插入到x的儿子中
 * 
 * @param x 被插入一个节点
 * @param y 要插入到x的根链表上的节点
 */
void FibHeap::LINK(FibHeap_Node* y, FibHeap_Node* x){
    if (this->min == y)
    {
        this->min = y->right;
    }
    remove_from_rootlist(y);
    if(x -> child == nullptr){
        x->child = y;
        x->degree ++;
        y->mark = false;
        y->p = x;
        y->right = y->left = y;
    }
    else{
        y->right = x->child->right;
        x->child->right->left = y;
        y->left = x->child;
        x->child->right = y;
        x->degree ++;
        y->p = x;
        y->mark = false;
    }
}


/**
 * @brief 关键字减值
 * 
 * @param x 需要减值的节点键值
 * @param k 目标值
 * 
 * @return 减值后堆的min的key
 */
int FibHeap::DECREASE_KEY(int l, int k){
    FibHeap_Node* x = &node_array[l];
    if (k>x->key)
    {
        cout << "new key is greater than current key\n";
        return 0;
    }
    x->key = k;
    FibHeap_Node* y = x->p;
    if (y != nullptr and x->key < y->key)
    {
        CUT(x, y);
        CASCADING_CUT(y);
    }
    if (x->key < this->min->key)
    {
        this->min = x;
    }
    return this->min->key;
}

void FibHeap::CUT(FibHeap_Node* x, FibHeap_Node* y){
    if (x == x->right)
    {
        y->child = nullptr;
    }
    else{
        x->left->right = x->right;
        x->right->left = x->left;
        if (y->child == x)
        {
            y->child = x->right;
        }
    }
    y->degree--;
    insert_into_rootlist(x);
    x->p = nullptr;
    x->mark = false;
}

void FibHeap::CASCADING_CUT(FibHeap_Node *y){
    FibHeap_Node* z = y->p;
    if(z == nullptr){
        if (y->mark == false)
        {
            y->mark = true;
        }
        else{
            CUT(y, z);
            CASCADING_CUT(z);
        }
    }
}


/**
 * @brief 从斐波那契堆中删除一个节点
 * 
 * @param x 待删除的节点的键值
 * 
 * @return 删除后堆的n
 */
int FibHeap::DELETE(int x){
    DECREASE_KEY(x, -100000);
    EXTRACT_MIN();
    return this->n;
}


/**
 * @brief 获取最小节点
 * 
 * @return int 返回最小节点的键值
 */
int FibHeap::MINIMUN(void){
    return this->min->key;
}